package test;

import instance.InstanceEj2;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
import java.util.Vector;

import output.Problem2Output;

import problem.ej2.Ej2;
import problem.ej2.Ejes_strings;

public class testEj2 {

	public static int[][] generarArbol(int n) {
		/* Genera un árbol con n nodos y pesos en las aristas entre 1 y 15 */
		/*
		 * Si vas a usar la función "agregarAristas" usá un n mayor o igual a 7
		 * (por cuestiones de densidad-esparcidad)
		 */
		int[][] res = new int[n][n];
		for (int i = 1; i < n; i++) {
			res[i - 1][i] = 1;
		}
		return res;
	}

	public static void agregarAristas(int[][] arbol, int n, int tipo) {
		/* IMPORTANTE: EL ÁRBOL DEBE TENER 7 O MÁS NODOS */
		/*
		 * Puede agregar o no ejes al árbol para hacerlo un poco menos disperso
		 * o no, respectivamente. Sé que el árbol tiene los ejes formando una
		 * "secuencia perfecta" (i,i+1) que a su vez forma un camino. Me Abuso
		 * de este hecho
		 */
		/*
		 * Calculo la cantidad de ejes que tengo que agregar usando la fórmula D
		 * = 2m/(n(n-1)) ==> m = D(n(n-1))/2
		 * Disperso: D = 0.4 aprox
		 * Denso: D = 0.81 aprox
		 * Completo D=1
		 */

		int constante = n * (n - 1) / 2;
		int m = 1;/* Para que no tire error */
		switch (tipo) {

		case 1: /* Tengo que hacerlo disperso */
			m = (int) Math.floor(0.40 * constante);
			break;
		case 2: /* Tengo que hacerlo denso */
			m = (int) Math.floor(0.81 * constante);
			break;
		case 3:
			m = constante;
			break;

		}

		int m_agregar = m - (n - 1);
		Vector<Coord> en_cero = new Vector<Coord>();
		for (int fila = 0; fila < n; fila++) {
			for (int col = fila + 1; col < n; col++) {
				Coord c = new Coord(fila, col);
				if (arbol[fila][col] == 0)
					en_cero.add(c);
			}
		}
		Collections.shuffle(en_cero);
		for (int i = 0; i < m_agregar; i++) {
			Coord a_1 = en_cero.lastElement();
			en_cero.removeElementAt(en_cero.size() - 1);
			arbol[a_1.fila][a_1.columna] = 1;
		}

	}

	public static LinkedList<Coord> PasarAListaDeCoord(int[][] arbol, int n) {
		LinkedList<Coord> res = new LinkedList<Coord>();

		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (arbol[i][j] == 1) {
					Coord l = new Coord(i , j);
					res.add(l);
				}
			}
		}

		return res;
	}

	public static InstanceEj2 PasarDeListaDeCoordAInstance(
			LinkedList<Coord> ejes, int n, int tipo) throws Exception {
		BufferedReader bufferedReader = new BufferedReader(new FileReader(
				new File("./src/resources/Ej2/lista-de-nombres.txt")));
		int i = 0;
		Vector<String> nombres = new Vector<String>(n);
		while (i < n) {
			String nombre = bufferedReader.readLine().trim();
			nombres.add(nombre);
			i++;
		}
		assert(nombres.size() == n);

		Collections.shuffle(nombres);
		int p = -1, q = -1;
		Random rnd = new Random();

		switch (tipo) {

		case 1: /* p y q están entre los vertices */
			p = rnd.nextInt(n);
			q = (p + n / 2) % n;
			break;
		case 2: /* solo q está entre los vértices */
			p = -1;
			q = rnd.nextInt(n);
			break;
		case 3: /* ninguno está entre los vértices */
			p = -1;
			q = -1;
			break;

		}

		/* Cara pos de nombre representa un vértice distinto */
		String st_p, st_q;
		if (p == -1)
			st_p = "asdasd";
		else
			st_p = nombres.get(p);
		if (q == -1)
			st_q = "assssd";
		else
			st_q = nombres.get(q);
		Ejes_strings p_y_q = new Ejes_strings(st_p, st_q);
		LinkedList<Ejes_strings> list_ejes = new LinkedList<Ejes_strings>();
		Iterator<Coord> it = ejes.iterator();
		while (it.hasNext()) {
			Coord c = it.next();
			Ejes_strings amistad = new Ejes_strings(nombres.get(c.columna),
					nombres.get(c.fila));
			list_ejes.add(amistad);
		}
		return new InstanceEj2(list_ejes, p_y_q);

	}

	public static void generarGrafoDisperso(int n, int tipo, String archsalida) throws Exception {
		/* IMPORTANTE: n>=7 */
		LinkedList<InstanceEj2> res = new LinkedList<InstanceEj2>();
		for (int i = 7; i < n; i++) {
			int[][] arbol = generarArbol(i);
			agregarAristas(arbol, i, 1);
			LinkedList<Coord> lista_grafo = PasarAListaDeCoord(arbol, i);
			InstanceEj2 inst = PasarDeListaDeCoordAInstance(lista_grafo, i, tipo);
			res.add(inst);
		}
		Problem2Output salida = new Problem2Output(archsalida);
		salida.writeInstance(res);
	}

	public static void generarGrafoDenso(int n, int tipo, String archsalida) throws Exception{
		/* IMPORTANTE: n>=7 */
		LinkedList<InstanceEj2> res = new LinkedList<InstanceEj2>();
		for (int i = 7; i < n; i++) {
			int[][] arbol = generarArbol(i);
			agregarAristas(arbol, i, 2);
			LinkedList<Coord> lista_grafo = PasarAListaDeCoord(arbol, i);
			InstanceEj2 inst = PasarDeListaDeCoordAInstance(lista_grafo, i, tipo);
			res.add(inst);
		}
		Problem2Output salida = new Problem2Output(archsalida);
		salida.writeInstance(res);
	}

	public static void generarGrafoCompleto(int n, int tipo, String archsalida) throws Exception{
		/* IMPORTANTE: n>=7 */
		LinkedList<InstanceEj2> res = new LinkedList<InstanceEj2>();
		for (int i = 7; i < n; i++) {
			int[][] arbol = generarArbol(i);
			agregarAristas(arbol, i, 3);
			LinkedList<Coord> lista_grafo = PasarAListaDeCoord(arbol, i);
			InstanceEj2 inst = PasarDeListaDeCoordAInstance(lista_grafo, i, tipo);
			res.add(inst);
		}
		Problem2Output salida = new Problem2Output(archsalida);
		salida.writeInstance(res);
		
	}
	public static void generarArbol(int n, int tipo, String archsalida) throws Exception{
		/* IMPORTANTE: n>=7 */
		LinkedList<InstanceEj2> res = new LinkedList<InstanceEj2>();
		for (int i = 7; i < n; i++) {
			int[][] arbol = generarArbol(i);
			LinkedList<Coord> lista_grafo = PasarAListaDeCoord(arbol, i);
			InstanceEj2 inst = PasarDeListaDeCoordAInstance(lista_grafo, i, tipo);
			res.add(inst);
		}
		Problem2Output salida = new Problem2Output(archsalida);
		salida.writeInstance(res);
	}

	public static void main(String[] args) throws Exception {
		generarGrafoCompleto(59, 1, "./src/resources/Ej2/p-y-q-estan/completo.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-y-q-estan/completo.in", true);
//		generarGrafoDenso(59, 1, "./src/resources/Ej2/p-y-q-estan/denso.in");
//			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-y-q-estan/denso.in", true);
		generarGrafoDisperso(59, 1, "./src/resources/Ej2/p-y-q-estan/disperso.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-y-q-estan/disperso.in", true);
		generarArbol(59, 1, "./src/resources/Ej2/p-y-q-estan/arbol.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-y-q-estan/arbol.in", true);
		System.out.println("Terminados Todos los 1");
		
		generarGrafoCompleto(59, 2, "./src/resources/Ej2/p-no-esta/completo.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-no-esta/completo.in", true);
//		generarGrafoDenso(59, 2, "./src/resources/Ej2/p-no-esta/denso.in");
//			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-no-esta/denso.in", true);
		generarGrafoDisperso(59, 2, "./src/resources/Ej2/p-no-esta/disperso.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-no-esta/disperso.in", true);
		generarArbol(59, 2, "./src/resources/Ej2/p-no-esta/arbol.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/p-no-esta/arbol.in", true);
		System.out.println("Terminados Todos los 2");
		
		generarGrafoCompleto(59, 3, "./src/resources/Ej2/ninguno-esta/completo.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/ninguno-esta/completo.in", true);
//		generarGrafoDenso(59, 3, "./src/resources/Ej2/ninguno-esta/denso.in");
//			Ej2.AlgoritmoPpal("./src/resources/Ej2/ninguno-esta/denso.in", true);
		generarGrafoDisperso(59, 3, "./src/resources/Ej2/ninguno-esta/disperso.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/ninguno-esta/disperso.in", true);
		generarArbol(59, 3, "./src/resources/Ej2/ninguno-esta/arbol.in");
			Ej2.AlgoritmoPpal("./src/resources/Ej2/ninguno-esta/arbol.in", true);
		System.out.println("Terminados Todos los 3");

	}

}